#include <iostream>
#include <unordered_map>
#include <set>
#include <cstring>
#include <queue>

using namespace std;

void dfs(int i,unordered_map<int,set<int>>& mp,int visited[]){
	if(visited[i]) return;
	
	visited[i] = 1;
	cout << i << ' ';
	if(mp.count(i)){
		for(auto j : mp[i]){
			if(!visited[j]){
				dfs(j,mp,visited);
			}
		}
	}
}

void bfs(unordered_map<int,set<int>>& mp,int visited[]){
	queue<int> que;
	que.push(1);
	visited[1] = 1;
	cout << 1 << ' ';
	while(!que.empty()){
		int size = que.size();
		for(int i = 0; i < size; ++i){
			int val =  que.front();
			que.pop();
			if(mp.count(val)){
				for(auto j : mp[val]){
					if(!visited[j]){
						visited[j] = 1;
						que.push(j);
						cout << j << ' ';
					}
				}
			}
			
		}
	}
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);

	int n,m;
	cin >> n >> m;
	unordered_map<int,set<int>> mp;
	int visited[n+1] = {0};
	while(m--){
		int i,j;
		cin >> i >> j;
		mp[i].insert(j);
	}
	dfs(1,mp,visited);
	cout << endl;
	memset(visited,0,sizeof(visited));
	bfs(mp,visited);
	return 0;
}

